﻿using System.Collections.Generic;

namespace DataStruct
{
    public class Node
    {
        public int Data;//数据元素
        public Node Next;//指向下一个节点的指针
        public Node(int data)
        {
            this.Data = data;
        }
    }

    /// <summary>
    /// 单链表
    /// </summary>
    public class LinkedList
    {
        public Node first;//头节点指针
        public Node last;//尾节点指针

        public LinkedList()
        {
            for (int i = 0; i <= 5; i++)
            {
                InsertInLast(i);
            }
        }

        /// <summary>
        /// 前插法--插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInHead(int data)
        {
            Node newNode = new Node(data);
            newNode.Next = first;//步骤1、将新节点的后驱指针指向first
            first = newNode;     //步骤2、将first指针指向新节点
            if (last == null)
            {
                last = newNode;
            }
        }

        /// <summary>
        /// 尾插法插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInLast(int data)
        {
            Node newNode = new Node(data);
            if (first == null)
            {
                first = newNode;
                last = newNode;
            }
            last.Next = newNode;//步骤1、将尾节点的后驱指针指向新节点
            last = newNode;//步骤2、将last指针指向新节点
        }

        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="data"></param>
        public void DeleteByValue(int data)
        {
            if (first == null)
            {
                return;
            }
            Node current = first;
            Node pre = null;

            while (current != null && current.Data != data)
            {
                pre = current;
                current = current.Next;
            }

            //没有找到要删除的节点
            if (current == null)
            {
                return;
            }
            //删除头节点
            if (current == first)
            {
                first = first.Next;
                if (first == null)
                {
                    last = null;
                }
                return;
            }
            //删除尾节点
            if (current == last)
            {
                pre.Next = null;
                last = pre;
                return;
            }
            //删除中间节点
            pre.Next = current.Next;
        }

        /// <summary>
        /// 删除:按索引删除 删除单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        public void DeleteByIndex(int index)
        {
            //删除第一个节点
            if (index == 1)
            {
                first = first.Next;
                if (first == null)
                {
                    last = null;
                }
                return;
            }

            Node current = first;
            Node pre = null;
            int i = 1;
            //找到第i个节点
            while (i != index)
            {
                pre = current;
                current = current.Next;
                i++;
            }

            pre.Next = current.Next;
            //如果是最后一个节点
            if (current.Next == null)
            {
                last = pre;
            }
        }

        /// <summary>
        /// 查找:按索引查找 查找单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public Node GetByIndex(int index)
        {
            Node currentNode = first;
            int i = 1;
            while (i != index)
            {
                currentNode = currentNode.Next;
                i++;
            }
            return currentNode;
        }

        /// <summary>
        /// 查找:按值查找
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public Node GetByData(int data)
        {
            Node currentNode = first;
            while (currentNode != null && currentNode.Data != data)
            {
                currentNode = currentNode.Next;
            }
            return currentNode;
        }

        /// <summary>
        /// 插入:在第index个位置插入数据data
        /// </summary>
        /// <param name="index"></param>
        /// <param name="data"></param>
        public void Insert(int index, int data)
        {
            int length = GetLength();
            //头节点插入
            if (index == 1)
            {
                InsertInHead(data);
                return;
            }
            //尾节点插入
            if (index > length)
            {
                InsertInLast(data);
                return;
            }
            //中间插入
            int i = 1;
            Node currentNode = first;
            Node preNode = null;
            while (i != index)
            {
                preNode = currentNode;
                currentNode = currentNode.Next;
                i++;
            }

            Node newNode = new Node(data);//步骤1、欲插入位置前一个节点的指针指向新节点
            newNode.Next = currentNode;//步骤2、新节点的指针指向欲插入位置的节点
            preNode.Next = newNode;
        }

        /// <summary>
        /// 链表拼接 将当前单链表和另一个单链表拼接
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public LinkedList Concatenate(LinkedList list)
        {
            if (last == null)
            {
                first = list.first;
                last = list.last;
                return this;
            }
            last.Next = list.first;
            last = list.last;
            return this;
        }

        /// <summary>
        /// 链表反转
        /// </summary>
        public void Reverse()
        {
            var tempFirst = first;
            var tempLast = last;
            Node current = first;
            Node pre = null;
            Node prepre = null;
            while (current != null)
            {
                prepre = pre;
                pre = current;
                current = current.Next;
                pre.Next = prepre;
            }

            first = tempLast;
            last = tempFirst;
        }

        /// <summary>
        /// 链表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return first == null || last == null;
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        /// <returns></returns>
        public void Clear()
        {
            first = last = null;
        }

        /// <summary>
        /// 获取链表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            int count = 0;
            Node current = first;
            while (current != null)
            {
                count++;
                current = current.Next;
            }
            return count;
        }

        /// <summary>
        /// 输出单链表
        /// </summary>
        public void Print()
        {
            if (first == null)
            {
                return;
            }

            Node current = first;
            while (current != null)
            {
                Console.Write($"{current.Data} ");
                current = current.Next;
            }
            Console.WriteLine($"头节点:{first.Data},尾节点:{last.Data},链表长度:{GetLength()}");
        }
    }
}
